home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / C / Applications / SML⁄NJ 93+ / Documentation / examples / union-find.sml < prev   
Encoding:
Text File  |  1995-12-30  |  664 b   |  24 lines  |  [TEXT/R*ch]
  1. (* Union-find algorithm *)
  2.  
  3. datatype 'a setelem 
  4.   = NILSET
  5.   | ELEM of 'a * 'a setelem ref * int ref
  6.  
  7. exception SETINFO
  8.  
  9. fun new_setelem x = ELEM(x, ref NILSET, ref 1)
  10.  
  11. fun set_union(NILSET, f) = f
  12.   | set_union(e, NILSET) = e
  13.   | set_union(e as ELEM(_,e_next,e_size), f as ELEM(_,f_next,f_size)) =
  14.       if !e_size < !f_size
  15.       then (f_size := !e_size + !f_size; e_next := f; f)
  16.       else (e_size := !e_size + !f_size; f_next := e; e)
  17.  
  18. fun find NILSET = NILSET
  19.   | find (e as ELEM(_,ref NILSET,_)) = e
  20.   | find (ELEM(_,f,_)) = let val g = find (!f) in (f := g; g) end
  21.  
  22. fun setinfo NILSET = raise SETINFO
  23.   | setinfo e = let val ELEM(x,_,_) = find e in x end
  24.